perm filename 1[4,BGB]1 blob
sn#075334 filedate 1973-12-05 generic text, type C, neo UTF8
COMMENT ā VALID 00003 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 4.1 The Winged Edge Polyhedron Representation.
C00005 00003 FIGURE - THE WINGED EDGE.
C00008 ENDMK
Cā;
4.1 The Winged Edge Polyhedron Representation.
A polyhedron in made up of four kinds of nodes: bodies,
faces, edges and vertices. The body node is the head of three rings:
a ring of faces, a ring of edges and a ring of vertices. Each face
and each vertex points at one of the edges on its perimeter. Each
edge points at its two faces and its two vertices. Completing the
structure, each edge node contains a link to each of its four
immediate neighboring edges clockwise and counter clockwise around
face (vertex) perimeters. These last four pointers are the wings of
the edge, which provide the basis for efficient face and vertex
perimeter accessing. Finally,the links of the edge nodes can be
ordered in a consistent fashion over the surface of any polyhedron so
that the surface always has two sides: the inside and the outside.
Klein bottles and worse are precluded by the data structure.
Observe that there are twenty-two link fields in the basic
representation: bodies contain six links, faces three, vertices three
and edges ten. Thus the least number of different link field names we
need to coin is ten; if we warn the reader in advance that a link
name such as PED has different roles depending on whether it applies
to a body, face, edge or vertex.
---------------------------------------------------------------------
TABLE Data Structure Link Names
1. Face Ring of a Body. NFACE PACE
2. Edge Ring of a Body. NED PED
3. Vertex Ring of a Body. NVT PVT
4. First Edge of a Vertex. PED
5. First Edge of a Face. PED
6. The two faces of an edge: NFACE PFACE
7. The two vertices of an edge: NVT PVT
8. The four wing edges of an edge: NCW PCW
NCCW PCCW
---------------------------------------------------------------------
FIGURE - THE WINGED EDGE.
(As viewed from the exterior of a solid).
\ /
NCCW(E) \ / PCW(E)
\ /
\ /
\ /
ā PVT(E)
|
|
NFACE(E) E PFACE(E)
|
|
NVT(E) ā
/ \
/ \
/ \
NCW(E) / \ PCCW(E)
/ \
A face, edge or vertex can only belong to one body and so
there is only one body node in a given face, edge or vertex ring; and
that body node serves as the head of the ring. The reason for double
pointer rings is for the sake of rapid deletion, which allows local
alterations to a polyhedron's topology without any list searching.
As figure 2.2 suggests, four of these eight pointers are
stored in the same positions and referred to by the same names as the
face and vertex ring pointers; namely the NFACE, PFACE, NVT and PVT
pointers.
There are four ways in which a pair of faces and a pair of
vertices can be placed into the two face positions and two vertex
positions of an edge. By constraining these choices edges can
independently indicate both a linear direction and a surface
orientation.
The single winged edge pointer found in faces and vertices is
kept in the position named PED and it points to one of the edges
belonging to that face or vertex. Although the vertices in figure 2.2
are shown with three edges, vertices may have any number of edges;
those other potential edges would not be directly connected to E and
so were not shown.